package com.demo.java.OD501_550.OD546;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【宽度最小的子矩阵(C卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146529342
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 解析输入
        int[] params = split(in.nextLine(), " ");
        int n = params[0]; // 矩阵的行数
        int m = params[1]; // 矩阵的列数
        int[][] matrix = new int[n][m];

        // 读取矩阵数据
        for (int i = 0; i < n; i++) {
            int[] temp = split(in.nextLine(), " ");
            for (int j = 0; j < m; j++) {
                matrix[i][j] = temp[j];
            }
        }

        // 读取目标数字集合
        int k = Integer.parseInt(in.nextLine());
        int[] nums = split(in.nextLine(), " ");

        // 每列数字出现的次数
        int[][] count_map = new int[m][1000];

        // 统计每列中各个数字出现的次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count_map[j][matrix[i][j]] += 1;
            }
        }

        // 统计目标数字的出现次数
        int[] target_map = new int[1000];
        for (int i = 0; i < k; i++) {
            target_map[nums[i]] += 1;
        }

        // 当前窗口的数字出现次数统计
        int[] cur_count_map = new int[1000];
        int width = Integer.MAX_VALUE; // 初始化宽度为最大值
        int left = 0, right = 0;

        // 滑动窗口
        while (true) {
            if (right >= m) {
                break;
            } else {
                // 向右扩展窗口
                for (int i = 0; i < 1000; i++) {
                    cur_count_map[i] += count_map[right][i];
                }

                // 窗口满足条件时，尝试收缩窗口
                while (check(cur_count_map, target_map)) {
                    if (right - left + 1 < width) {
                        width = right - left + 1; // 更新最小宽度
                    }

                    // 收缩左边界
                    for (int i = 0; i < 1000; i++) {
                        cur_count_map[i] -= count_map[left][i];
                    }
                    left += 1;
                }
            }
            right += 1;
        }

        // 输出结果
        if (width == Integer.MAX_VALUE) {
            System.out.println(-1); // 没有找到满足条件的子矩阵
        } else {
            System.out.println(width); // 输出最小宽度
        }
    }

    // 字符串转整数数组
    public static int[] split(String input_str, String chars) {
        String[] tmp2 = input_str.split(chars);
        int[] nums = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {
            nums[i] = Integer.parseInt(tmp2[i]);
        }
        return nums;
    }

    // 检查当前窗口是否包含所有目标数字
    public static boolean check(int[] cur_map, int[] target_map) {
        for (int i = 0; i < 1000; i++) {
            if (cur_map[i] < target_map[i]) {
                return false; // 如果某个目标数字的数量不足，返回 false
            }
        }
        return true; // 窗口包含所有目标数字，返回 true
    }
}